#include <iostream>
#include <vector>

using namespace std;

const int N = int(1e6 + 10);

struct Node
{
    int data;
    int nums;
    Node(int d, int n = 1)
    {
        data = d;
        nums = n;
    }
    Node()
    {
        data = 0;
        nums = 0;
    }
};

int& Data(Node& tmp)
{
    return tmp.data;
}

int& Nums(Node& tmp)
{
    return tmp.nums;
}

bool empty(Node q[])
{
    return Data(q[N - 2]) == Data(q[N - 1]);
}

bool full(Node q[])
{
    return (Data(q[N - 1]) + 1 - Data(q[N - 2])) % (N - 2) == 0;
}

int size(Node q[])
{
    return Nums(q[N - 1]);
}

int query(Node q[])
{
    if (empty(q))
        return ~(1 << 31);
    int top = Data(q[N - 2]);
    return Data(q[top]);
}

int rquery(Node q[])
{
    if (empty(q))
        return ~(1 << 31);
    int rtop = Data(q[N - 1]);
    rtop = (rtop + N - 3) % (N - 2);
    return Data(q[rtop]);
}

void push(Node q[], int x)
{
    if (full(q))
        return;
    Nums(q[N - 1])++;
    int& tail = Data(q[N - 1]);
    if (rquery(q) == x)
    {
        int tmp = (tail + N - 3) % (N - 2);
        Nums(q[tmp])++;
        return;
    }
    Data(q[tail]) = x;
    Nums(q[tail]) = 1;
    tail = (tail + 1) % (N - 2);
}

void push(Node q[], int x, int n)
{
    if (full(q))
        return;
    Nums(q[N - 1]) += n;
    int& tail = Data(q[N - 1]);
    if (rquery(q) == x)
    {
        int tmp = (tail + N - 3) % (N - 2);
        Nums(q[tmp]) += n;
        return;
    }
    Data(q[tail]) = x;
    Nums(q[tail]) = n;
    tail = (tail + 1) % (N - 2);
}

void rpush(Node q[], int x)
{
    if (full(q))
        return;
    Nums(q[N - 1])++;
    int& rtail = Data(q[N - 2]);
    int& rtop = Data(q[N - 1]);
    if (Data(q[rtail]) == x)
    {
        Nums(q[rtail])++;
        return;
    }
    rtail = (rtail + N - 3) % (N - 2);
    Data(q[rtail]) = x;
    Nums(q[rtail]) = 1;
}

void rpush(Node q[], int x, int n)
{
    if (full(q))
        return;
    Nums(q[N - 1]) += n;
    int& rtail = Data(q[N - 2]);
    int& rtop = Data(q[N - 1]);
    if (Data(q[rtail]) == x)
    {
        Nums(q[rtail]) += n;
        return;
    }
    rtail = (rtail + N - 3) % (N - 2);
    Data(q[rtail]) = x;
    Nums(q[rtail]) = n;
}

int pop_some(Node q[])
{
    if (empty(q))
        return ~(1 << 31);
    int& top = Data(q[N - 2]);
    int& tail = Data(q[N - 1]);
    int tmp = Data(q[top]);
    Nums(q[N - 1]) -= Nums(q[top]);
    top = (top + 1) % (N - 2);
    return tmp;
}

int pop_single(Node q[])
{
    if (empty(q))
        return ~(1 << 31);
    int& top = Data(q[N - 2]);
    int& tail = Data(q[N - 1]);
    int tmp = Data(q[top]);
    Nums(q[top])--;
    Nums(q[N - 1])--;
    if (Nums(q[top]) == 0)
        top = (top + 1) % (N - 2);
    return tmp;
}

int rpop_some(Node q[])
{
    if (empty(q))
        return ~(1 << 31);
    int& rtop = Data(q[N - 1]);
    rtop = (rtop + N - 3) % (N - 2);
    Nums(q[N - 1]) -= Nums(q[rtop]);
    return Data(q[rtop]);
}

int rpop_single(Node q[])
{
    if (empty(q))
        return ~(1 << 31);
    int& rtop = Data(q[N - 1]);
    int left_rtop = (rtop + N - 3) % (N - 2);
    Nums(q[left_rtop])--;
    Nums(q[N - 1])--;
    if (Nums(q[left_rtop]) == 0)
        rtop = (rtop + N - 3) % (N - 2);
    return Data(q[left_rtop]);
}

void reset(Node q[])
{
    Data(q[N - 2]) = Data(q[N - 1]);
    Nums(q[N - 1]) = 0;
}

int a[N];
Node b[N];

int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    for (int i = 1; i < k; i++)
    {
        while (!empty(b) && rquery(b) > a[i - 1]) rpop_some(b);
        push(b, a[i - 1], i - size(b));
    }
    
    for (int i = k; i <= n; i++)
    {
        while (!empty(b) && rquery(b) > a[i - 1]) rpop_some(b);
        push(b, a[i - 1], k - size(b));
        printf("%d ", pop_single(b));
    }

    printf("\n"); reset(b);

    for (int i = 1; i < k; i++)
    {
        while (!empty(b) && rquery(b) < a[i - 1]) rpop_some(b);
        push(b, a[i - 1], i - size(b));
    }

    for (int i = k; i <= n; i++)
    {
        while (!empty(b) && rquery(b) < a[i - 1]) rpop_some(b);
        push(b, a[i - 1], k - size(b));
        printf("%d ", pop_single(b));
    }
}